In digital computer networks such as the Internet, collections of data, referred to as “datagrams,” are typically transferred from node to node over the network in packets. Each packet of data typically includes a header portion and a data portion. In accordance with the common Internet protocol (IP), the header portion typically includes a 32-bit source identifying portion which identifies the source node that originated the packet and a 32-bit destination identifying portion which identifies the destination node to which the packet is ultimately to be transferred.
At each node, a router is used to forward the packet to the next node in the path toward the destination node. When a router receives a packet, it examines the destination address in the packet header. It then searches its locally stored routing table to determine the next node to which the packet should be transferred in order to ensure that it will reach its destination, typically along the shortest possible path. The router then forwards the packet to the next node identified in the routing table. This process continues at each successive node until the destination node is reached.
Another technique used to forward packets which can be implemented in IP routers is referred to as multiprotocol label switching (MPLS), or simply label switching. In MPLS, a path or route, referred to as a label-switched path (LSP), through a label-switched network or subnetwork is created before actual data traffic is forwarded over the network. The LSP directs the forwarding of datagrams from a given ingress point to a given egress point in the bounded network or subnetwork.
In general, any pair of network nodes may be directly connected by more than one physical link. These physical links are equivalent to each other in the sense that a packet may be sent over any of them without affecting the way it is delivered to the ultimate destination. A set of such links comprises a single “logical link.” This configuration is referred to herein as “multiple parallel links.” In traditional IP forwarding, data traffic for a particular source and destination, i.e., a “flow,” should always travel along the same link to ensure that data packets are not misaligned in time when they arrive at the destination node. Therefore, a router must select one of multiple links for transmission of data packets to the next link, and, for each source/destination pair, it must select the same link to ensure proper alignment of data at the destination. The router typically performs an analysis of the packet header contents to assign each packet to a physical link. Usually this involves a hash function of the 5-tuple of fields in the IP header (source IP address, destination IP address, protocol, source port number, destination port number) or a subset of these fields, such as source IP address and destination IP address. A hash function is designed to perform a computation on one or more data words and return a unique data word of shorter length. For example, a hash function performed on two 32-bit IP addresses may divide the combined 64-bit word by a constant and return as a result the value of the remainder in fewer bits, e.g., five. Other hash procedures include the use of a cyclic redundancy check (CRC) and the use of a checksum. Each time a hash procedure is performed on the same initial values, the same result is obtained. Therefore, deriving the link assignment from such a hash ensures that all packets with the same field contents take the same physical link, and thus all packets of a given application flow also take the same link. This ensures that the existence of multiple links does not contribute to the risk of misordered packets within a flow.
In MPLS packet forwarding, MPLS can be used to route some traffic over a path other than the shortest one in order to relieve congestion on some paths. In a label switching network, paths are set up in advance for given sets of traffic that are to be forwarded along the same path. A set of traffic that is to follow the same paths is commonly referred to as a forwarding equivalence class (FEC). The ingress router can create label-switched paths (LSPs) to each of the other edge routers to which it expects to send traffic, and it can make all the decisions about the routes taken by the packets it forwards. It can do so by asking each downstream router in the path to assign a label value to the path. Using a signaling protocol such as RSVP or LDP, the ingress node sends a path setup request signal along the desired path to request labels from each of the nodes in the path. When the signal reaches the egress node, the egress node begins the process of allocating labels for the path. The egress node sends its allocated label back to the next preceding node, which stores the label and generates its own label for the traffic and transmits that label back to its next preceding node. This continues until all of the nodes along the path have assigned labels for the given FEC traffic.
When the ingress router desires to send a packet along a path, it places a small header, referred to as the MPLS header, on the front of the packet. The MPLS header contains the label value assigned by the next router in the path. The router then forwards the packet with the new MPLS header to the next router, which removes the label from the packet and replaces it with the label assigned by the next router. The packet is then forwarded to the next router. This continues until the packet has been forwarded over the entire LSP, i.e., it reaches the egress router. The egress router knows that it is at the end of the LSP, so it removes the MPLS header from the packet and forwards the packet on the network using the traditional IP destination address lookup.
In MPLS, the labels assigned by the nodes identify the route to be taken from node to node along the LSP, but they do not readily provide the ability to distinguish multiple physical parallel links within the route or path. One reason for this is that it is difficult to compute an IP address hash at each node or “hop,” as is done in IP forwarding, because the IP header is “hidden” behind the MPLS header. Hence, the hash procedure, which may be usable to select one of many paths, is not readily adaptable to MPLS. One of the features of MPLS is that the LSP carries opaque traffic, that is, the end points of the LSP know what protocol is carried, but the interior nodes do not. This feature could allow MPLS to be used to create virtual private networks that carry other protocols as well as IP. This means that an interior node cannot reliably compute an address hash, because it does not know anything about the contents of the packet behind the first MPLS header. Furthermore, even if it is known that all packets carry IP datagrams, there is a problem knowing where the IP header is located within the packet. This is because MPLS permits a stack of label headers to be added to the front of a packet. The label header format includes a single bit indicating the last label before the encapsulated protocol begins, meaning that the position of the encapsulated header must be found by examining the label headers, one-by-one, until the last one is found.
Conventional MPLS suffers a drawback in that, with conventional MPLS, it is relatively inefficient to set up multiple parallel paths to distribute traffic over multiple parallel physical links. In particular, each individual path needs to be independently signaled, i.e., set up. This signaling becomes particularly inefficient when there are a large number of potential parallel paths.